1. Field of the Invention
The present invention relates to a method and an apparatus for motion estimation, and more particularly, to a method using hierarchical search to estimate motion vectors and an apparatus thereof.
2. Description of the Related Art
The motion estimation is the most complicated computing area in terms of the computing amount in the video compression encoder, which also affects the compression result the most. Accordingly, there are many fast algorithms that had been proposed to reduce the computing amount and the memory usage, which also sustains sufficient compression quality.
Among various fast algorithms, the hierarchical search is an algorithm that effectively reduces both of the computing amount and the memory usage. A hierarchical search method that can generate variable blocks had been proposed by J. H. Lee [1] as shown in the flow chart of FIG. 1.
Referring to FIG. 1, first a low pass filtering and a subsampling are performed on the original frame data 111 and the reference frame data 112 in steps 101 and 102, such that three different resolution layers are obtained. They are the original resolution layer, the medium resolution layer, and the lowest resolution layer. Wherein, the original resolution layer contains the original frame data 111 and the reference frame data 112, the medium resolution layer contains the data generated in step 101, and the lowest resolution layer contains the data generated in step 102.
Then, in step 103, a wide range search is performed on the lowest resolution layer, so as to obtain three motion vectors. They are two optimal motion vectors and one predicated motion vector that is obtained from the video standard. Then, in step 104, a local search is performed on the medium resolution layer. Wherein, both of the searches performed in the lowest resolution layer and the medium resolution layer mentioned above use a block size of 16×16. Finally, in step 105, a local search is performed on the original resolution layer on the vicinity of the motion vectors obtained from the medium resolution layer. Meanwhile, the original 16×16 block is split into four 8×8 smaller blocks. And finally the optimal block mode and the motion vector 113 are selected. The drawback of such method is that the motion vectors of small blocks are limited by a very small range. Thus it is not possible to effectively estimate the case where the physical motion vectors between small blocks are far away from each other.
The document referred by the method mentioned above is: [1] J. H. Lee, et. al., “A fast multi-resolution block matching algorithm and its LSI architecture for low bit-rate video coding,” IEEE Trans. Circuits and Systems for Video Technology, vol. 11, no. 12, pp. 1289-1301, December 2001.